import java.awt.geom.PathIterator;

class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }

    public ListNode(int val,ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class PartitionList {
    public static void main(String[] args) {
        //创建链表6->5->3->4->2->1->1->7
        ListNode p1 = new ListNode(6);
        ListNode p2 = new ListNode(5);
        ListNode p3 = new ListNode(3);
        ListNode p4 = new ListNode(4);
        ListNode p5 = new ListNode(2);
        ListNode p6 = new ListNode(1);
        ListNode p7 = new ListNode(1);
        ListNode p8 = new ListNode(7);
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;
        p5.next = p6;
        p6.next = p7;
        p7.next = p8;

        ListNode node = partition(p1,4);
        while(node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    public static ListNode partition(ListNode head , int x) {
        ListNode bigHead = null, bigTail = null;    //>=x 的区域
        ListNode smallHead = null, smallTail = null;//< x 的区域
        ListNode next = null; //记录当前节点的下一个位置

        while(head != null) {
            next = head.next;
            head.next = null; //与下一节点断链

            if(head.val >= x) {  //走大链表位置
                if(bigHead == null) { //判断是否第一次进入大链表
                    bigHead = head;
                }else {
                    bigTail.next = head;
                }
                bigTail = head;
            }else {             //走小链表位置
                if(smallHead == null) {
                    smallHead = head;
                } else {
                    smallTail.next = head;
                }
                smallTail = head;
            }

            head = next; //重新找到下一节点
        }
        if(smallHead == null) {
            return bigHead;
        }
        smallTail.next = bigHead;  //连接上大小列表  小链表的尾巴连接上大链表的头部

        return  smallHead;
    }
}

